The present invention has particular applicability with respect to the enhancement of image data obtained from the scanning of a fingerprint. The data enhancement according to the present invention comprises a first step in an apparatus and method for (1) the further refining of data defining an image, for example, a fingerprint, (2) the classification of the refined image, and (3) the matching of the particular image to data in a data bank containing data representative of features of an image, for example, a fingerprint image, according to the presence and location of certain types of identifying characteristics, e.g., fingerprint minutia found in the refined image.
It is known in the art to process fingerprint image data in order to refine the fingerprint image, classify the refined image and match the minutia found in the refined image to a data bank containing minutia data. The present invention relates to an improved method and apparatus for enhancing the image data prior to the steps of refinement, classification and identification. The invention may also be useful for enhancing images in arts other than the classification and identification of fingerprints. The enhanced data output may also be utilized with data which is not representative of an image per se. However, for purposes of illustration the method and apparatus of the present invention will be described in terms of enhancement of fingerprint image data prior to further processing of the enhanced data.
The art of fingerprint classification and identification has utilized an input image in the form of a matrix of data elements in the form of pixels derived from the scanning of a fingerprint image with a digital camera to form a digitized binary image consisting of a matrix of pixels having a value of either 1 or 0, representing, respectively, white or black. The art has processed this binary image with a technique known as thin fill and a technique known as angflow in order to classify the fingerprint according to type and to locate and define minutia within the fingerprint image as is shown by the U.S. Pat. Nos. 4,003,024, 4,083,035, 4,151,512, 4,156,230 and 4,225,850 assigned to the assignee of the present invention, the disclosures of which are hereby incorporated by reference.
In the past, the binary image data has been generated by comparing the data in the individual image pixels within the matrix to a mean value of the possible intensities and assigning a 0 if the intensity is below that mean and a 1 if the intensity is above that mean. For various reasons, the image may be of poor quality or may be of poor quality in certain locations. For example, in a fingerprint there are instances where the fingerprint may be only partially retrievable or the fingerprint may be partially smudged. The digitizing of the image intensity data as performed in the prior art, has a number of drawbacks when the image is of poor quality as a whole or in certain parts. The errors induced into the binary image as a result of, in effect making a guess as to the high intensity or low intensity nature of the image data at a given image pixel carry forward through the remainder of the refinement, classification and identification processes known in the art. This may result in the inability to properly classify or properly to identify the image, e.g., the fingerprint, even where a matching print in fact is within the data storage memory of the fingerprint identification system.
The present invention seeks to improve the apparatus and method used in deriving binary image and direction data for each data element from the camera input image intensity for each image pixel obtained from an image source, e.g., a digital camera. Aspects of processing of the data in accordance with certain parts of the invention may be implemented on a microprocessor or minicomputer suitably programmed to perform the various logic and arithmetic functions explained below. However, such implementation of the present invention would require a great deal of computing power and time. Therefore, the applicants have incorporated into the apparatus and method of the present invention specifically dedicated hardware circuits which improve by several thousand times the speed with which the data enhancement process could be performed on, for example, a programmed minicomputer or microprocessor.
One invention described herein encompasses the various algorithms for contextual enhancement of image data as implemented in either software or hardware. Software implementation enables, in comparison to the prior art, a much more accurate and precise computer matching of a blurred, poorly defined print with a file print. Thus, with the use of such software, programmed to carry out the logic operations disclosed herein, a very poor grade fingerprint, being blurred, smudged or otherwise lacking in good definition of various portions, may be processed to provide a much clearer, well defined print that can be readily matched to a file print. Although such software implementation will provide significant enhancement of the poor print, it does require a large amount of time to enhance the fingerprint image in order to generate the fingerprint minutia data used for each print comparison, and thus suffers severe disadvantages in commercial application.
Described herein, and illustrated in the drawings, is a hardware invention comprising new and improved apparatus and methods for carrying out contextual image enhancement with vastly increased speed of operation and very high-quality results. This hardware according to the present invention, constitutes a major improvement over the software and enables the apparatus to develop minutia data for a fingerprint image in approximately 900 milliseconds, whereas the software implementation may require approximately 35 minutes to develop such minutia data for each print.
Other examples of images which may be enhanced according to the present invention are, for example, digitized photographic data taken under conditions of very low light or at great distance, or under conditions of high shadow in certain areas of the photograph. In addition, image data, e.g., representing features defined and extracted by optical character readers, and many types of contour patterns, including those developed in conjunction with geographical and geological mapping, structure analysis and wave analysis, may be enhanced according to the principles of the present invention. Similarly, data, e.g., relating to speech or other sound patterns may be enhanced according to the present principles of the invention.
Recognizing the need for an improved data enhancer useful in enhancing image data and the like, a general object of the present invention is to provide an apparatus and method for producing an improved enhancement of the data contained in a data array of a matrix of data elements, and, more specifically, in the preferred embodiment as described, a data array consisting of a matrix of pixels containing image intensity data.
Before highlighting some of the features of the apparatus and method of the present invention, it will be helpful to outline the entire apparatus and method. The apparatus which mechanizes the method of the present invention is set up to analyze data in three basic scan windows which are clocked through a matrix array of data elements each containing either intensity data, direction data or both. The first window and its associated circuitry serve to estimate data element directions by analyzing the intensity data in selected direction slits in the window to establish the slit having the least summed contrast between data elements spaced apart in the slit by a selected number of data elements, or to establish that there does not clearly exist such a slit. The second window passes through the matrix such that its data elements have already been passed through the preliminary direction estimate window and have a preliminary direction estimate of one of the slit directions or "no direction." This second window and its associated circuitry enhance the direction estimates (made during passage of the first window) according to various logic tests which generally seek to identify a slit direction which, along with the directions adjacent to it, are the directions of the predominate number of data elements in the window, or which is the average the two slit directions which comprise the largest and second largest number of data elements, if they are sufficiently close in direction. The final window examines data elements having enhanced directions and with its associated circuitry, enhances the intensity data of a center data element in the third window, provided the center data element has an enhanced direction other than "no direction," according to an analysis of the center data element and the neighboring slit data elements in the slit with the direction of the enhanced direction of the center data element. The center data element and the neighboring slit data elements are compared with each other for direction data and intensity data and are compared with a mean intensity value for the scan window to derive a correction value for the center data element intensity to arrive at an enhanced intensity value. Separate logic is used to enhance the center data element intensity when it has a direction of "no direction."
A feature of the present invention is an improved method of enhancement of data contained a data element within the matrix of the data element array through the analysis of data contained in surrounding data elements comprising a window of data elements positioned within the matrix of the data element array.
Another feature of the present invention is the stepping of the window through the data array in a stepwise fashion, column by column and row by row to sequentially enhance the data contained in a center data element of the window.
Yet another feature of the present invention is to sequentially employ several such windows, each being in registration with the other such that the output of an enhancing step performed in one window is serially input into the next succeeding window as such output is available for a center data element in the preceding window, in order to further perform steps to enhance the data in a center data element in the succeeding window.
Still another feature of the present invention is to enhance the data in a central data element within a particular window by operations performed on the data contained within the window which are independent of the actual location of the data elements within the window, e.g., a compilation of the distribution of data throughout the window or, e.g., the mean of the particular data throughout the window. This feature includes updating the results of these operations for the purpose of enhancing the data in a center data element of a next succeeding position of the window by a two axis window update. This involves storing the change necessary to update the compilation of the data within the data elements of the window from a prior first window location to a prior succeeding window location, and updating the necessary change for moving the center data element from a present first window location to the present succeeding window location, by examining the changes resulting from data elements disposed at generally the corners of the present first window location and adding these changes to the change which was necessary between the prior first window location and succeeding window location. These data elements are selected to constitute the difference between the previous update of the compilation of data elements in the window and the present update of the compilation of the data elements in the window.
It is still another feature of the present invention to provide circuitry for the parallel evaluation of the relationship of a plurality of different selected data elements within the window as it passes through the matrix, simultaneously for each particular location of a window within the data array.
Yet a further feature of the present invention is to first assign a preliminary direction estimate for each data element within the array based upon the contrast of intensity values in selected spaced apart data elements defining selected directions within a window, and second to enhance the direction estimate based upon the distribution of preliminary direction estimates within a window, and third to enhance the intensity data of a center data element, having been assigned an enhanced direction, based upon the comparison of the direction data contained in selected data elements defining a slit within a window. The slit selected is the one aligned with the enhanced direction assigned the center data element. Another factor employed in the intensity enhancement step is the variance of the intensity data in each such selected data element from the mean intensity of all data elements within the window. Yet another factor employed is the variance of the direction of each such data element in the slit from the direction assigned the center data element.
Yet a still further feature of the present invention is to assign a preliminary direction estimate to each center data element for each position of a first scan window by defining within the window a plurality of selected data elements comprising slits, respectively aligned as closely as practicable to each of a set of line directions generally equally separated within the window and passing through the center data element. A slit sum is generated for each slit comprised of the accumulated sum of the differences of the intensity data values for pairs of spaced apart data elements in the slit, separated by a selected number of data elements. A determination is then made of which of the slit sums is the lowest and the dynamic range of all intensity values for the window. A preliminary direction estimate of the direction of the slit having the lowest slit sum is assigned the center data element. This is done unless the dynamic range is below a selected threshold, or too many of the slit sums of the closely aligned slits or any of the slit sums of the unaligned slits fail to exceed the lowest slit sum by some percentage of the lowest slit sum, in which event a direction of "no direction" is assigned. The closely aligned slits have directions within a selected number of degrees of the slit having the lowest slit sum, and the unaligned slits do not.
Again another feature of the present invention is to enhance the direction data for a center data element within a second scan window, regardless of whether the center data element has a direction or "no direction" as a preliminary direction estimate, by generating a histogram of a number of data elements within the window having each of the possible slit directions, including "no direction," and selecting an enhanced direction based upon the occurrence of a sufficient number of data elements with closely aligned directions. The direction of the histogram bin with the highest number count of data elements, which have the same slit direction, is selected as the enhanced direction if the sum of this bin and the bins containing the count of the number of data elements with adjacent slit directions exceeds a threshold number. The bin from the histogram with the second highest number count of data elements, which have the same direction, is selected if the first condition is not met and the sum of the second highest bin number and the number contained in the bins designated by slit directions adjacent to the direction of the second high bin number exceeds the threshold. If no enhanced direction has been assigned by the preceding steps, the direction of the high bin number is selected if the sum of the high bin number and its adjacent bins exceeds a second threshold and the sum of the high bin number and its adjacent bins plus the number in the "no direction" bin exceeds a third threshold. If the preceding tests are not met the direction of the second high bin number is selected if the sum of the number count in the second high bin and its adjacent direction bins exceeds the second threshold and the count in the second high bin, and its adjacent bins, plus the number in the "no direction" bin, exceeds the third threshold. If the preceding tests have not been met, the average of the direction of the high bin and the second high bin is selected if the sum of the numbers in those bins exceeds a fourth threshold or the sum of the high bin and second high bin numbers exceed the fifth threshold, and the sum of the high bin and second high bin plus the number count in the " no direction" bin, exceeds the third threshold. The directions associated with the respective first and second high bins also must not be separated from each other by more than a selected number of degrees. If the above-noted tests are not met, the enhanced direction assigned is "no direction."
Again yet a further feature of the present invention is the enhancement of the intensity data in a data element by comparing that data element with a third scan window containing enhanced direction data and intensity data. If the center data element in the window has an assigned direction other than "no direction," then the mean intensity within the scan window is compared to the dynamic range within the window. If the mean intensity is equal to or greater than a selected percentage of the dynamic range, then the mean intensity is adjusted by the addition of a constant value. If, instead, the mean intensity is equal to or less than a smaller percentage of the dynamic range, then the mean value is adjusted by the subtraction of a fixed constant.
A further feature of the present invention is the enhancement of the intensity data in a data element by comparing the center data element of the scan window with the data contained in each of a plurality of neighboring data elements defining a slit aligned with the slit direction of the center data element.
If the local dynamic range, i.e., the dynamic range of the data elements within the intensity enhancement scan window, is large and the intensity of the center data element is nearly equal to the adjusted local mean, i.e., the mean of the intensity values of the data elements within the intensity enhancement scan window, incremented or decremented by a constant adjustment factor, then the intensity of the center data element is set equal to the adjusted local mean. Provided the respective neighboring slit data elements have other than "no direction" assigned, the intensity of each such neighboring slit data element is compared with the adjusted mean intensity for the data elements in the third window. If the dynamic range is large and the difference between the adjusted mean intensity and the intensity of a neighboring slit data element is small, then the neighboring slit data element is ignored in the enhancement calculations. If not, then an intensity enhancement value contribution is computed for each such neighboring slit data element. The value of each contribution is proportional to the difference between the intensity of each such neighboring data element and the adjusted mean intensity. Each intensity enhancement value contribution has a signed multiplication factor to decrease the intensity of the center data element when the intensity of the neighboring data element is less than the adjusted mean and to increase the intensity of the center data element when the intensity of the neighboring data element exceeds the adjusted mean, for each neighboring slit data element in which the difference in direction between the neighboring slit data element and the center data is less than a selected number of degrees. The intensity enhancement value has a signed multiplication factor to increase the intensity of the center data element when the intensity of the neighboring data element in the slit is less than the adjusted mean and to decrease the intensity of the center data element when the intensity of the neighboring slit data element exceeds the adjusted mean, for each neighboring data element with a direction differing from the center data element by more than the selected number of degrees. The sum of these intensity enhancement value contributions is divided by a constant and this result is added to the center data element intensity to become the enhanced intensity for this data element.
If the center data element in the scan window has "no direction," then the intensity enhancement is based on local statistical data. If the intensity of the center data element is greater than the local mean and the local dynamic range is small, then the enhanced intensity for the center data element is set equal to its original intensity value plus a constant.
If the intensity of the center data element is greater than the local mean, and the local dynamic range is large, and the intensity of the center data element is less than the average of the local mean and the upper limit of the local dynamic range (usually the 90 percentile intensity value), then the enhanced intensity is set to equal to the average of the local mean and upper limit of the dynamic range. If the intensity of the center data element is greater than the local mean, and the local dynamic range is large and the intensity of the center data element is equal to or greater than the average of the local mean and the upper limit of the dynamic range, then the enhanced intensity for the center data element is set equal to the average of its original intensity and the upper limit of the dynamic range.
If the intensity of the center data element is less than the local mean and the dynamic range is small, the enhanced intensity for the center data element is set equal to its original intensity minus a constant.
If the intensity of the center data element is less than the local mean, and the dynamic range is large, and the intensity of the center data element is greater than the average of the local mean and the lower limit of the local dynamic range (usually the 10 percentile intensity value), then the enhanced intensity value for the center data element is set equal to the average of the local mean and the lower limit of the local dynamic range.
If the intensity of the center data element is less than the local mean, and the dynamic range is large, and if the intensity of the center data element is equal to or less than the average of the local mean and the lower limit of the local dynamic range, then the enhanced intensity for the center data element is set equal to the average of its original value and the lower limit of the local dynamic range.
The foregoing features are not intended to be exhaustive, but rather are intended to illustrate the advantages of the present invention over the prior art and to enable one skilled in the art to better understand the present invention and the contribution to the art. These and other advantages and features of the present invention will be better understood by reference to the detailed description of a preferred embodiment set forth below in conjunction with the drawing, in the figures of which like reference numerals have been used to identify like elements.